package com.ocean.greedy.medium;

/**
 * https://leetcode.cn/problems/jump-game-ii/
 * <p>
 * <p>
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * <p>
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * <p>
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 * <p>
 * <p>
 * <p>
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
 * 示例 2:
 * <p>
 * 输入: nums = [2,3,0,1,4]
 * 输出: 2
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 1000
 * 题目保证可以到达 nums[n-1]
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/22 <br>
 */
public class JumpGameII2 {

    public static void main(String[] args) {
        JumpGameII2 jum = new JumpGameII2();
        int[] nums = {2, 3, 1, 1, 4};
        int res = jum.jump(nums);
        System.out.println(res);
        int[] nums2 = {2, 3, 0, 1, 4};
        res = jum.jump(nums2);
        System.out.println(res);
    }

    // [2,3,0,1,4]
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        int curDistance = 0;
        int ans = 0;
        int nextDistance = 0;
        for (int i = 0; i < n - 1; i++) {
            // 算出下一步可以覆盖的距离
            nextDistance = Math.max(i + nums[i], nextDistance);
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
            }
        }
        return ans;
    }


}
